package com.future;

import java.util.ArrayList;
import java.util.List;

/**
 * Description: 120. 三角形最小路径和（用例没过完）
 *
 * @author weiruibai.vendor
 * Date: 2022/10/31 15:04
 */
public class Solution_120 {

    public static void main(String[] args) {
        // [[2],[3,4],[6,5,7],[4,1,8,3]]
        List<List<Integer>> triangle = new ArrayList<>();
        triangle.add(new ArrayList<Integer>() {{
            add(2);
        }});
        triangle.add(new ArrayList<Integer>() {{
            add(3);
            add(4);
        }});
        triangle.add(new ArrayList<Integer>() {{
            add(6);
            add(5);
            add(7);
        }});
        triangle.add(new ArrayList<Integer>() {{
            add(4);
            add(1);
            add(8);
            add(3);
        }});
        System.out.println(minimumTotal_v2(triangle));
    }

    /**
     * -   2
     * -  3 4
     * - 6 5 7
     * 4 1 8 3
     * 整理成下面这样
     * -      2
     * -    5   6
     * -  11 10  13
     * -15  11  18  16
     * 过程解释
     * row=0时
     * list={2}
     * row=1
     * list={5,6}
     * row=2
     * list={11,*,13}
     * 这里的*，路径可有两条，所以选择最优的，因为求的是最小只，所以求min
     * ...
     *
     * @param triangle
     * @return
     */
    public static int minimumTotal_v2(List<List<Integer>> triangle) {
        List<Integer> list = new ArrayList<>();
        int N = triangle.size();
        list.addAll(triangle.get(0));
        int row = 1;
        while (row < N) {
            List<Integer> curList = triangle.get(row);
            list = calcSpesificLine(list, curList);
            row++;
        }
        int ans = Integer.MAX_VALUE;
        for (Integer num : list) {
            ans = Math.min(ans, num);
        }
        return ans;
    }

    private static List<Integer> calcSpesificLine(List<Integer> list, List<Integer> curList) {
        List<Integer> newList = new ArrayList<>();
        int N = curList.size();
        // 填左边界
        newList.add(list.get(0) + curList.get(0));
        for (int i = 1; i < N - 1; i++) {
            // 路径可有两条，所以选择最优的，因为求的是最小只，所以求min
            newList.add(Math.min(list.get(i - 1), list.get(i)) + curList.get(i));
        }
        // 填右边界
        newList.add(list.get(N - 2) + curList.get(N - 1));
        return newList;
    }

}

